1
Mendefinisikan Masalah Konveks dalam Bentuk Standar
MATH008Lesson 4
00:00

Masalah optimisasi konveks dalam bentuk standar merupakan dasar dari pemrograman matematis modern. Masalah ini didefinisikan oleh fungsi tujuan konveks $f_0$, kendala ketidaksamaan konveks $f_i$, dan affin kendala kesamaan. Dengan mendefinisikan masalah di atas irisan domain-domain ini $\mathcal{D} = \bigcap_{i=0}^m \text{dom } f_i$, kita memastikan bahwa setiap optimal lokal adalah optimal global.

1. Anatomi Matematis dalam Bentuk Standar

Masalah ini secara formal dinyatakan sebagai:

$$\begin{aligned} &\text{minimalkan} && f_0(x) \\ &\text{dengan syarat} && f_i(x) \leq 0, \quad i = 1, \dots, m \\ &&& a_i^T x = b_i, \quad i = 1, \dots, p \end{aligned}$$

Himpunan layak didefinisikan sebagai $\text{dom } F = \{x \in \text{dom } f_0 \mid f_i(x) \le 0, i = 1, \dots, m, h_i(x) = 0, i = 1, \dots, p \}$. Persyaratan kritis untuk kekonveksan adalah bahwa kendala kesamaan harus affin ($Ax = b$), karena kesamaan non-linier umumnya menghasilkan himpunan yang tidak konveks.

2. Interpretasi Geometris dalam Bentuk Epigraf

Bentuk epigraf memungkinkan kita untuk menafsirkan optimisasi secara geometris dalam ruang 'grafik' $(x, t)$. Dengan memperkenalkan variabel sela $t$, kita meminimalkan $t$ dengan syarat $(x, t) \in \text{epi } f_0$. Ini menunjukkan bahwa himpunan layak, himpunan sublevel apa pun, dan himpunan optimal bersifat konveks secara inheren.

3. Jebakan Implisit vs. Eksplisit

Kesalahpahaman umum adalah bahwa memindahkan kendala ke dalam fungsi tujuan (menjadikannya implisit) menyederhanakan masalah. Namun, menjadikan kendala implisit tidak membuat masalah lebih mudah dianalisis atau diselesaikan, meskipun masalah hasilnya secara nominal tidak memiliki kendala. Hal ini terutama berlaku dalam model model Oracle (kotak hitam), di mana kita mengevaluasi $f(x)$ dan turunannya dengan biaya tanpa mengetahui struktur eksplisitnya.

4. Aplikasi Dunia Nyata

  • Teori Portofolio: Meminimalkan risiko $\text{var}(c^T x) = x^T \Sigma x$ untuk 4 aset (misalnya, Aspek 1 dengan return 12%/SD 20%).
  • Teknik Sipil: Kendala struktural seperti $y_i = 6(i - 1/3) \frac{F}{E w_i h_i^3} + v_{i+1} + y_{i+1}$.
  • Probabilitas: Kendala risiko kerugian $\Phi^{-1}(\beta) \leq 0$.
🎯 Prinsip Utama
Kondisi optimal untuk $f_0$ yang dapat didiferensialkan diberikan oleh $\nabla f_0(x)^T(y - x) \geq 0$ untuk semua $y$ yang layak. Ini menyiratkan bahwa gradien harus menjadi bidang pendukung terhadap himpunan layak pada titik optimal.